#include "Sort.h"
#include "Stack.h"

void PrintArray(int* p, int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", p[i]);
    }
    printf("\n");
}

void Swap(int* pa, int* pb)
{
    int tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

void InsertSort(int* p, int n)
{
    
    for (int i = 0; i < n - 1; ++i)
    {
        int end = i;
        //保存end前面的数据
        int tmp = p[end + 1];
        //当end为
        while (end >= 0)
        {
            //升序，判断tmp小于p[end]
            if (tmp < p[end])
            {
                //小于则覆盖end后面的数据
                p[end + 1] = p[end];
                --end; //end往后移
            }
            else
            {
                break;
            }
        }
        //当end走到-1时，放在循环里面处理会导致数组越界访问，进而程序崩溃
        p[end + 1] = tmp;
    }
}

void ShellSort(int* p, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //比如有1000个数，gap之间的间隔为"334"，第二次间隔为112次，第三次间隔为"38",第四次为"13"，第五次为"5", 第六次为"2"(前面为"预排序"),最后为"1"进行(插入排序)
        gap = gap / 3 + 1;
        //插入排序的变形，插入排序一次走一步，而希尔走gap步
        //当gap > 1时，进行预排序-----当gap等于1时，说明已经接近有序，进行插入排序
        //一开始进行排序时，i必须小于n - gap，如果i < n时，会导致tmp赋值时，会导致越界
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = p[end + gap];
            while (end >= 0)
            {
                if (tmp < p[end])
                {
                    p[end + gap] = p[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            p[end + gap] = tmp;
        }
    }
}

void BubbleSort(int* p, int n)
{
    //冒泡排序：如果进行升序排序，p[i]大于p[i + 1]时进行交换，大的往后移...
    //第一次走n趟，第二次走n - 1，第三次n - 2.....则判断可以写成n - i
    for (int i = 0; i < n; ++i)
    {
        for (int j = 1; j < n - i; ++j)
        {
            if (p[j - 1] > p[j])
            {
                Swap(&p[j - 1], &p[j]);
            }
        }
    }
}

//当快排遇到最坏情况时(有序数组)，每次递归进行排序找的left都是最小的，通过等差数列(n-1+n-2+...+0)得出时间复杂度为O(N^2)，当数据量越大时，会导致"栈溢出"(递归太深，无法释放)
//这里针对这一劣势进行优化，使用"三数取中"：选的不是最大的，也不是最小的，而是选出"中位数"
int GetMidIndex(int* p, int left, int right)
{
    int mid = left + (right - left) / 2;

    if (p[mid] > p[left])
    {
        if (p[mid] < p[right])
        {
            return mid;
        }
        else if (p[left] > p[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    //p[mid] < p[left]
    else
    {
        if (p[mid] > p[right])
        {
            return mid;
        }
        else if (p[left] < p[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

//hoare版本
int PartSort1(int* p, int left, int right)
{
    int mid = GetMidIndex(p, left, right);
    Swap(&p[mid], &p[left]);

    int key = left;
    while (left < right)
    {
        //key在最左边，先走right,找比key小的值
        while (p[key] <= p[right] && left < right)
            --right;

        //right向后走找到比key小的值后，left往前走找比key大的值
        while (p[key] >= p[left] && left < right)
            ++left;

        //当left走到大于key并且right走到小于key的值时，进行交换
        Swap(&p[left], &p[right]);
    }
    //当left和right相遇时，交换key和它们其中一个的值
    Swap(&p[key], &p[left]);

    return left;
}

//挖坑法->比较好理解，不用考虑left和right相遇时为什么比key小！
//不用理解左边是key时，为什么要右边先走的问题！
int PartSort2(int* p, int left, int right)
{
    int mid = GetMidIndex(p, left, right);
    Swap(&p[mid], &p[left]);

    //首先保存最左边的值
    int key = p[left];
    //建坑位
    int pit = left;
    while (left < right)
    {
        //首先从右边开始走，找比key小的数据
        while (key <= p[right] && left < right)
        {
            --right;
        }
        //覆盖坑位数据
        p[pit] = p[right];
        //更新新的坑位
        pit = right;

        //右边找完完后，走左边，左边找比key大的值的
        while (key >= p[right] && left < right)
        {
            ++left;
        }
        //覆盖坑位数据
        p[pit] = p[left];
        //更新新的坑位
        pit = left;
    }
    //出了循环后说明left和right相遇了，只有一个坑位
    //把key的数据给到pit
    p[pit] = key;

    return pit;
}

//前后指针版本---->思想：cur比key小时，前置自增prev，交换cur与prev数据，cur比key大时，自增cur，cur走到right(尾)时，说明prev小于key，交换prev与key(a[left])的内容
//注意：cur是一直往前走的
int PartSort3(int* p, int left, int right)
{
    //int mid = GetMidIndex(p, left, right);
    //Swap(&p[mid], &p[left]);

    int prev = left;
    int cur = left + 1;
    int key = p[left];

    //当cur走到尾时，退出循环
    while (cur <= right)
    {
        //当p[cur]小于key并且p[++prev]不等于p[cur]时，交换数据，等于就直接跳过
        if (p[cur] < key && p[++prev] != p[cur])
            Swap(&p[prev], &p[cur]);

        //自增cur
        ++cur;
    }

    //cur走到尾时，prev位置的值一定比key小，交换key位置和prev的内容
    Swap(&p[prev], &p[left]);

    return prev;
}

void QuickSort1(int* p, int begin, int end)
{
    //当begin不在其所在区间中时，说明已经排序完，回归递归
    if (begin >= end)
        return;

    //hoare版本
    //int keyi = PartSort1(p, begin, end);

    //挖坑法
    //int keyi = PartSort2(p, begin, end);

    //前后指针版本
    int keyi = PartSort3(p, begin, end);

    //递归进行排序---->[begin, key - 1] key [key + 1, end]
    //左子树：[begin, key - 1]
    QuickSort1(p, begin, keyi - 1);

    //右子树：[key + 1, end]
    QuickSort1(p, keyi + 1, end);

}

//"小区间优化版本"
void QuickSort2(int* p, int begin, int end)
{
    //当begin不在其所在区间中时，说明已经排序完，回归递归
    if (begin >= end)
        return;

    //hoare版本
    //int keyi = PartSort1(p, begin, end);

    //挖坑法
    //int keyi = PartSort2(p, begin, end);

    if (end - begin + 1 >= 10)
    {
        InsertSort(p + begin, end - begin + 1);
    }
    else
    {
        //前后指针版本
        int keyi = PartSort3(p, begin, end);

        //递归进行排序---->[begin, key - 1] key [key + 1, end]
        //左子树：[begin, key - 1]
        QuickSort1(p, begin, keyi - 1);

        //右子树：[key + 1, end]
        QuickSort1(p, keyi + 1, end);
    }
}

//非递归版本
void QuickSort3(int* p, int begin, int end)
{
    ST st; //声明栈
    StackInit(&st); //初始化栈

    //将begin和end入栈，待排序时需要使用
    StackPush(&st, begin);
    StackPush(&st, end);

    while (!StackEmpty(&st))
    {
        //栈："先进后出"，栈顶的值是end，将它赋值给对应的right，然后出栈
        int right = StackTop(&st);
        StackPop(&st);
        //将栈中的begin赋给left，然后出栈
        int left = StackTop(&st);
        StackPop(&st);

        //使用"前后指针版本"进行排序
        int key = PartSort3(p, left, right); //进行排序

        //排序后：[left, key - 1] key [key + 1, right]
        //key左区间：[left, key - 1]
        if (left < key - 1)
        {
            StackPush(&st, left);
            StackPush(&st, key - 1);
        }

        //key右区间：[key + 1, right]
        //当key+1大于right时说明key不在区间中[0+1, 0]----当key+1等于right时说明只有一个值[0, 0]
        if (key + 1 < right)
        {
            StackPush(&st, key + 1);
            StackPush(&st, right);
        }
        //这里是先进行key右区间排序，因为栈的性质("先进后出")
    }
    StackDestory(&st);
}

void SelectSort(int* p, int n)
{
    //找数组中最大值和最小值，然后交换到最左边和最右边里面
    int left = 0;
    int right = n - 1;
    while (left < right)
    {
        int Max = right, Min = left;
        for (int i = left; i <= right; ++i)
        {
            //在左闭右闭[left, right]区间中找最大值和最小值
            if (p[i] > p[Max])
                Max = i;

            if (p[i] < p[Min])
                Min = i;
        }
        //交换数据
        Swap(&p[left], &p[Min]);

        //如果left和Max重叠，则需修正
        if (left == Max)
            Max = Min;

        Swap(&p[right], &p[Max]);

        //更新left和right
        ++left;
        --right;
    }
}

void AdjustDown(int* p, int n, int root)
{
    //一开始父节点为根节点
    int parent = root;
    int child = (parent * 2) + 1; // 求左孩子节点

    while (child < n)
    {
        //找左右子树最大的节点
        if (p[child + 1] > p[child] && child + 1 < n)
            ++child;

        //控制调整为"大堆"
        if (p[parent] < p[child])
        {
            //交换父节点和子节点的值
            Swap(&p[parent], &p[child]);
            //更新父节点和孩子节点
            parent = child;
            child = (parent * 2) + 1;

        }
        else
        {
            //在中间调整完成时，直接跳出循环
            break;
        }
    }
}

void HeapSort(int* p, int n)
{
    //向下调整"建大堆"
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(p, n, i);
    }

    //排序
    int end = n - 1;
    while (end > 0)
    {
        //交换根节点和尾结点
        Swap(&p[0], &p[end]);
        //然后从"根节点"开始向下调整
        AdjustDown(p, end, 0);
        //忽略最后的节点
        --end;
    }
}

void _MergeSort(int* p, int begin, int end, int* tmp)
{
    //begin等于end时说明区间为[0, 0]只有一个值，begin大于end时说明区间不存在[1, 0]（mid为0时）
    if (begin >= end)
        return;

    int mid = begin + (end - begin) / 2;
    //分割数组--->分成二个区间 [begin, mid] [mid+1, end]
    _MergeSort(p, begin, mid, tmp);
    _MergeSort(p, mid + 1, end, tmp);

    //归并分割后的数据
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int index = begin;

    //使用二叉树中“后序遍历的方法"进行排序并且"归并到原数组" --- 跟合并二个数组和链表相似-> 取小进行尾插(升序)
    while (begin1 <= end1 && begin2 <= end2)
    {
        //取小放到辅助数组
        if (p[begin1] < p[begin2])
        {
            tmp[index++] = p[begin1++];
        }
        else
        {
            tmp[index++] = p[begin2++];
        }
    }

    //二个区间中可能还会存在数据没有入到辅助数组tmp的情况
    while (begin1 <= end1)
        tmp[index++] = p[begin1++];

    while (begin2 <= end2)
        tmp[index++] = p[begin2++];

    //将排序好的辅数组(tmp)拷贝到原数组(p)中
    memcpy(p + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* p, int n)
{
    //动态开辟一个辅助数组
    int* tmp = (int*)malloc(sizeof(int) * n);

    //排序
    _MergeSort(p, 0, n - 1, tmp);
}

void MergeSortNonR(int* p, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    assert(tmp);
    //一开始gap为1，两两进行归并
    int gap = 1;

    //gap等于或大于n说明已经合并完成
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            int index = i;

            //判断边界问题
            if (end1 >= n)
                end1 = n - 1;

            //当"end2越界时，修正end2"
            if (end2 >= n)
                end2 = n - 1;

            //当b"begin2未越界且end2越界时，修正end2"
            if (begin2 < n && end2 >= n)
                end2 = n - 1;

            //当"begin2和end2都越界时"，说明是一个不存在的区间，修正为不进循环的区间
            if (begin2 >= n && end2 >= n)
            {
                begin2 = n;
                end2 = n - 1;
            }

            while (begin1 <= end1 && begin2 <= end2)
            {
                if (p[begin1] < p[begin2])
                {
                    tmp[index++] = p[begin1++];
                }
                else
                {
                    tmp[index++] = p[begin2++];
                }
            }
            while (begin1 <= end1)
                tmp[index++] = p[begin1++];

            while (begin2 <= end2)
                tmp[index++] = p[begin2++];
        }
        //将归并好的辅助数组(tmp)拷贝回原数组中
        memcpy(p, tmp, sizeof(int) * n);

        //每次归并的间隔为2的倍数，第一次gap为1，第二次为2，第三次为4......
        gap *= 2;
    }
}